package HojaT6;
import hojat6.huffmanTree;
import hojat6.node;
import structure5.PriorityVector;
import structure5.SinglyLinkedList;
import structure5.PriorityQueue;
import structure5.List;
import java.util.Iterator;
import java.util.Scanner;
import structure5.BinaryTree;
import structure5.VectorHeap;

public class huffman2
{
    public static void main(String args[])
    {
        List<node> freqnodo = new SinglyLinkedList<node>();
        Scanner teclado = new Scanner(System.in);
        String sentencia = teclado.next();
        
        //PriorityQueue<huffmanTree> arbol = new PriorityVector<huffmanTree>();
        VectorHeap<huffmanTree> arbol = new VectorHeap<huffmanTree>();
        
        // read data from input
        for (int i=0; i<sentencia.length(); i++)
        {
            char c = sentencia.charAt(i);

            // look up character in frequency list
            node query = new node(c);
            node item = freqnodo.remove(query);
            if (item == null)
            {   // not found, add new node
                freqnodo.addFirst(query);
            } else { // found, increment node
                item.incrementarFrec();
                freqnodo.addFirst(item);
            }
        }
        // insert each character into a huffman tree
        
        for (node n : freqnodo)
        {
            arbol.add(new huffmanTree(n));
        }

        // merge trees in pairs until one remains
        while (arbol.size() > 1)
        {
            // grab two smallest values
            huffmanTree smallest = (huffmanTree)arbol.remove();
            huffmanTree small = (huffmanTree)arbol.remove();
            // add bigger tree containing both
            //trees.add(new huffmanTree(smallest,small));
            arbol.add(new huffmanTree(smallest,small));
           
        }
        huffmanTree encoding = arbol.remove();
        encoding.print();
        
        //Decodificar el texto.
        int numero=0;
        String sentenciadecod=teclado.next();
        while(numero<sentenciadecod.length()){
            huffmanTree nodoInteres = encoding;
            
            if(sentenciadecod.charAt(numero) =='0'){
                
                while(nodoInteres.isLeft()){
                    System.out.println(nodoInteres.obtenerIzquierda());
                }
                
            }else if(sentenciadecod.charAt(numero) =='1'){
                while(nodoInteres.isRight()){
                    System.out.println(nodoInteres.obtenerDerecha());
                }
            }
            numero++;
        }
            
        }
}
